package leetcode;

import java.util.*;

/**
 * @Classname MergeKLists_0023
 * @Author happytaohaha
 * @Date 2020/3/11
 * @Description 合并K个排序链表
 */
public class MergeKLists_0023 {


    /**
     * 两两合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        } else if (len == 1) {
            return lists[0];
        } else {
            for (int i = 1; i < len; i++) {
                lists[0] = mergeList(lists[0], lists[i]);
            }
            return lists[0];
        }
    }

    private ListNode mergeList(ListNode list, ListNode list1) {
        ListNode head = new ListNode(-1);
        ListNode res = head;
        while (list != null && list1 != null) {
            if (list.val < list1.val) {
                res.next = list;
                list = list.next;
            } else {
                res.next = list1;
                list1 = list1.next;
            }
            res = res.next;
        }
        if (list != null) {
            res.next = list;
        }
        if (list1 != null) {
            res.next = list1;
        }
        return head.next;
    }


    /**
     * 暴力法 把所有的值都放入到一个list中，然后再排序返回
     * 遍历所有的值需花费O(N) 的时间。
     * 一个稳定的排序算法花费O(NlogN) 的时间。
     * 遍历同时创建新的有序链表花费O(N) 的时间。
     * 复杂度 O(NlogN)
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < lists.length; i++) {
            while (lists[i] != null) {
                list.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        Integer[] array = list.toArray(new Integer[0]);
        Arrays.sort(array);
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        for(int i = 0; i< array.length; i++){
            temp.next = new ListNode(array[i]);
            temp =  temp.next;
        }
        return head.next;
    }


    /**
     * 优先队列的方法
     * @param lists
     * @return
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {return null;}
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) {return -1;}
                else if (o1.val == o2.val) {return 0;}
                else {return 1;}
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            if (node != null) {queue.add(node);}
        }
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null) {queue.add(p.next);}
        }
        return dummy.next;
    }


    /**
     * 分治的方法
     * @param lists
     * @return
     */
    public ListNode mergeKLists3(ListNode[] lists) {
        if (lists == null || lists.length == 0) {return null;}
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {return lists[left];}
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {return l2;}
        if (l2 == null) {return l1;}
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }



}
